package chapter03;

public class HasPathSum112 {
    /**
     * 深度优先遍历
     * 到达叶子节点判断路径之和是否等于target 返回结果
     * process(x,sum,target) 来到节点x时 之前路径上值之和为sum 判断到达叶子节点时路径上值之和是否等于target
     * 递归出口
     *  1).x.left==null&&x.right==null
     *      return (sum+x.val)==target
     *  2).其他情况
     *      res=false
     *      if x.left!=null
     *          res|=process(x.left,sum+x.val,tartget)
     *      if x.right!=null
     *          res|=process(x.right,sum+x.val,tartget)
     *      return res
     */
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        return process(root,0,targetSum);
    }

    public boolean process(TreeNode x,int sum,int tartget){
        if(x.left==null&&x.right==null){
            return (sum+x.val)==tartget;
        }
        boolean res=false;
        if(x.left!=null){
            res|=process(x.left,sum+x.val,tartget);
        }
        if(x.right!=null){
            res|=process(x.right,sum+x.val,tartget);
        }
        return res;
    }
}
